Drawings of trees usually don't come alone, but are included in some text which is itself typeset by a text processing system. Therefore, a typical scenario is a pipe of three stages. First comes the tree drawing program which calculates the positioning of the nodes of the tree to be drawn and outputs a description of the tree drawing in some graphics language; next comes a graphics system which transforms this description into an intermediate language which can be interpreted by the output device; and finally comes the text processing system which integrates the output of the graphics system into the text.
This scenario loses its linear structure once nodes have to be labelled, since the labelling influences the positioning of the nodes. Labels usually occur inside, to the left of, to the right of, or beneath nodes (the latter only for external nodes), and their extensions certainly should be taken into account by the tree drawing algorithm. But the labels have to be typeset first in order to determine their extensions, preferably by the typesetting program that is used for the regular text, because this method makes for the uniformity in the textual parts of the document and provides the author with the full power of the text processing system for composing the labels. Hence, a more complex communication scheme than a simple pipe is required.
Although a system of two processes running simultaneously might be the most elegant solution, we wanted a system that is easily portable to a large range of hardware at our sites including personal computers with single process operating systems. Therefore, we thought of using a text processing system having programming facilities powerful enough to program a tree drawing algorithm and graphics facilities powerful enough to draw a tree. One text processing system rendering outstanding typographic quality and good enough programming facilities is TEX, developed by Knuth at Stanford University; see [10]. The TEX system includes the following programming facilities:
Although the programming facilities of TEX hardly exceed the abilities of a Turing machine, they are sufficient to handle relatively small programs. How about the graphics facilities? Although TEX has no built-in graphics facilities, it allows the placement of characters in arbitrary positions on the page. Therefore, complex pictures can be synthesized from elementary picture elements treated as characters. Lamport has included such a picture drawing environment in his macro package LATEX, using quarter circles of different sizes and line segments (with and without arrow heads) of different slopes as basic elements; see [11]. These elements are sufficient for drawing trees.
This survey of TEX's capabilities implies that TEX may be a suitable text processing system to implement a tree drawing algorithm directly. We are basing our algorithm on the RT algorithm, because this algorithm gives the aesthetically most pleasing results. In the first version presented here, we restrict ourselves to unary-binary trees, although our method is applicable to arbitrary multiway trees. But in order to take advantage of the text processing environment, we expand the algorithm to allow labelled nodes.
In contrast to previous tree drawing programs, we feel no necessity to position the nodes of a tree on a fixed grid. While this may be reasonable for a plotter with a coarse resolution, it is certainly not necessary for TEX, a system that is capable of handling arbitrary dimensions and produces device independent output.